package nf.traversal;

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.NoSuchElementException;
import nf.graph.Graph;
import nf.graph.Node;

public class PairwiseTraverser extends Traverser
{
	protected ArrayList<Node> nodes;
	private Node node;
	private int length;
	private int nodeIndex;
	private int pairIndex;
	
	public PairwiseTraverser(Graph network)
	{
		super(network);
		
		nodes = new ArrayList<Node>(network);
		length = nodes.size();
		nodeIndex = 0;
		pairIndex = 1;
		node = null;
	}
	
	protected void eliminateNodes()
	{
		int paired = pairIndex - 1;
		nodes.remove(paired);
		nodes.remove(nodeIndex);
		pairIndex = nodeIndex + 1;
		node = null;
		length -= 2;
	}
	
	// XXX: does not yet support directed graphs!
	
	public boolean hasNext()
	{
		return (pairIndex < length || nodeIndex < (length - 2));
	}
	
	public List<Node> next()
	{
		if (node == null && length > nodeIndex) {
			node = nodes.get(nodeIndex);
		}
	
		if (pairIndex >= length) {
			nodeIndex++;
			node = (length > nodeIndex)
				? nodes.get(nodeIndex)
				: null;
			pairIndex = (nodeIndex + 1);
		}
		
		if (nodeIndex >= (length - 1)) {
			throw new NoSuchElementException();
		}
		
		List<Node> pair = new ArrayList<Node>(2);
		Collections.addAll(pair, node, nodes.get(pairIndex++));
		return pair;
	}
	
	public static class Factory implements TraverserFactory
	{
		public Traverser createTraverser(Graph network)
		{
			return new PairwiseTraverser(network);
		}
	}
}
